import java.util.*;
public class Test {
    /*
    题目 1 ：分发饼干
     */
    //假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
    //对每个孩子 i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。
    // 如果 s[j]>= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。
    // 你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int i = 0;
        int j = 0;
        int count = 0;

        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            }else{
                j++;
            }
        }
        return count;
    }

    /*
    题目 2 ：摆动序列
     */
    //如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。
    // 第一个差（如果存在的话）可能是正数或负数。
    // 仅有一个元素或者含两个不等元素的序列也视作摆动序列。
    //子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
    //给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
    public static void main1(String[] args) {
        int[] nums = {1,17,5,10,13,15,10,5,16,8};
        int ret = wiggleMaxLength(nums);
    }

    public static int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }

    /*
    题目 3 : 最大子数组和
     */
    //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    //子数组 是数组中的一个连续部分。
    //动态规划：
    //自己的写法
    public int maxSubArray1(int[] nums) {
        int max = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.length; i++){
            sum += nums[i];
            if(sum < nums[i]){
                sum = nums[i];
            }
            if(sum > max){
                max = sum;
            }
        }
        return max;
    }

    //官方写法，更为简练一点
    public int maxSubArray(int[] nums) {
        int cur = 0;
        int max = nums[0];
        for(int x : nums){
            cur = Math.max(cur + x , x);
            max = Math.max(cur, max);
        }
        return max;
    }


}
